package main

import (
	"fmt"
	"math"
	"reflect"
	"unsafe"
)

type visit struct {
	p     uintptr
	extra int
	t     reflect.Type
}

type visitMap map[visit]reflect.Value

func mapIter(m reflect.Value) *reflect.MapIter {
	return m.MapRange()
}

func Clone(v interface{}) interface{} {
	if v == nil {
		return v
	}

	val := reflect.ValueOf(v)
	cloned := clone(val, nil)
	return cloned.Interface()
}

func clone(v reflect.Value, visited visitMap) reflect.Value {
	switch v.Kind() {
	case reflect.Map:
		return cloneMap(v, visited)
	case reflect.Slice:
		return cloneSlice(v, visited)
	default:
		panic(fmt.Errorf("go-clone: <bug> unsupported type `%v`", v.Type()))
	}
}

func cloneMap(v reflect.Value, visited visitMap) reflect.Value {
	if v.IsNil() {
		return reflect.Zero(v.Type())
	}

	t := v.Type()

	if visited != nil {
		visit := visit{
			p: v.Pointer(),
			t: t,
		}

		if val, ok := visited[visit]; ok {
			return val
		}
	}

	nv := reflect.MakeMap(t)

	if visited != nil {
		visit := visit{
			p: v.Pointer(),
			t: t,
		}
		visited[visit] = nv
	}

	for iter := mapIter(v); iter.Next(); {
		nv.SetMapIndex(clone(iter.Key(), visited), clone(iter.Value(), visited))
	}

	return nv
}

func cloneSlice(v reflect.Value, visited visitMap) reflect.Value {
	if v.IsNil() {
		return reflect.Zero(v.Type())
	}

	t := v.Type()
	num := v.Len()

	if visited != nil {
		visit := visit{
			p:     v.Pointer(),
			extra: num,
			t:     t,
		}

		if val, ok := visited[visit]; ok {
			return val
		}
	}

	c := v.Cap()
	nv := reflect.MakeSlice(t, num, c)

	if visited != nil {
		visit := visit{
			p:     v.Pointer(),
			extra: num,
			t:     t,
		}
		visited[visit] = nv
	}

	// For scalar slice, copy underlying values directly.
	if isScalar(t.Elem().Kind()) {
		src := unsafe.Pointer(v.Pointer())
		dst := unsafe.Pointer(nv.Pointer())
		sz := int(t.Elem().Size())
		l := num * sz
		cc := c * sz
		copy((*[math.MaxInt32]byte)(dst)[:l:cc], (*[math.MaxInt32]byte)(src)[:l:cc])
	} else {
		for i := 0; i < num; i++ {
			nv.Index(i).Set(clone(v.Index(i), visited))
		}
	}

	return nv
}

func isScalar(k reflect.Kind) bool {
	switch k {
	case reflect.Bool,
		reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
		reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr,
		reflect.Float32, reflect.Float64,
		reflect.Complex64, reflect.Complex128,
		reflect.String, reflect.Func,
		reflect.UnsafePointer,
		reflect.Invalid:
		return true
	}

	return false
}
